The present invention relates to methods and apparatus for rendering three-dimensional images on a computer display screen. More specifically, the present invention relates to methods and apparatus for managing the level of detail while rendering the geometry information of three-dimensional images.
Three-dimensional images, such as three-dimensional objects or terrain images, are typically rendered on a computer display screen by projecting a two-dimensional photographic image onto a geometric model. The photographic image furnishes two-dimensional details typically found in a two-dimensional photograph while the geometric model provides the texture and perspective regarding the third dimension. If the three-dimensional image to be rendered represents a terrain map, for example, the two-dimensional image may represent a photograph of the area. The geometric model onto which the two-dimensional image is projected provides the perspective regarding the peaks and valleys of the terrain.
As is widely known in the art, the geometric or perspective information may be modeled by a plurality of polygons, e.g., triangles. In a given image on the computer display screen, the level of detail of a rendered object is directly related to the number of polygons employed to model it. By way of example, FIG. 1A illustrates the rendition of an object 10 of an image 12 at a fairly coarse level of detail. In FIG. 1A, object 10 is modeled by four polygonal faces of which three faces (2, 4, and 6) are shown. In contrast to FIG. 1A, object 10 of FIG. 1B employs a greater number of polygonal faces to model itself and therefore can provide a finer level of detail. Note that in both FIGS. 1A and 1B, the two dimensional photograph that is typically projected onto the geometric model has been omitted for clarity.
While a greater number of polygons generally provides a higher level of detail, the use of a large number of polygons to model a particular image may impose too high a computational load on the computer to permit the computer to adequately model the image at a given frame rate. In rendering the geometry information of 3-dimensional objects, it is therefore important to perform level of detail (LOD) management to balance the appropriate level of detail to be presented to the user and the computational load on the computer itself.
Typically, the management of the LOD is performed as a function of the distance between a particular portion of the image to an eye point. For example, it is recognized that objects within the image that are further away from the eye point can be rendered with less detail, i.e., employing fewer polygons, without significantly affecting the fidelity of the rendered image. As the object moves closer to the eye point, a greater number of polygons may be employed to model that object in greater detail. By way of example, an airplane at the horizon may be represented by two triangles, representing the two wings. As the eye point moves closer to the plane, a greater number of polygons may be required to model the curvature of the wings and other details of the airplane such as the body, the windows, and the like. A well thought-out LOD management approach would reduce the overall number of polygons required to render a three-dimensional image while preserving the apparent fidelity of the rendered image.
In the prior art, management of the levels of detail is performed in a discrete manner. Under this approach, a given object in the image may be represented internally at multiple levels of detail. As the eye point moves toward or away from an object, its polygonal model changes instantaneously to reflect the appropriate level of detail given its distance to the eye point. However, since the change in the levels of detail occurs in a discrete manner, the visual effect is rather abrupt and may be readily noticed by the user as jarring, visually discontinuous motion. In the rendering of a terrain map, for example, users may see a new hill popping up out of the ground instantaneously as they increase its level of detail by moving an eye point toward a seemingly smooth ground portion.
In the prior art, the image to be rendered is modeled initially, i.e., at the start of a frame, by polygons at their coarsest level of detail, i.e., by the base polygons. A set of rules is then provided for subdividing these base polygons into smaller and smaller child polygons to represent portions of the image at finer and finer levels of detail. Under this prior art approach, objects which are closer to the eye point are modeled by a greater number of polygons, which are generated dynamically during run time from the coarser parent polygons.
Although this prior art approach gives the appearance of a continuum in the levels of detail, there are several disadvantages. For example, some virtual reality or simulation product requires a fairly fast frame rate, typically around 30 frames per second. Consequently, the computer only has at most 1/30th of a second to perform its modeling task for a given image. Since the prior art requires that the numerous child polygons, which are employed for modeling the objects close to the eye point, be generated on the fly, a high computational load is imposed on the computer while rendering the image. For images which are, for example, large, complex, or highly detailed, the high computational load imposed by the prior art dynamic approach may require an unduly large amount of time to complete the modeling task. When this happens, time may run out before modeling is completed for a given frame. When this happens, the computer may be forced to either slow the frame rate down to allow the modeling task to be completed or to proceed with rendering the incompletely modeled image in order to keep up the required frame rate. As can be appreciated, either alternative is less than desirable.
In view of the foregoing, what is needed are improved methods and apparatus for managing the levels of detail of objects in the rendition of three-dimensional images on a computer display screen.